Les graphes TP



Les graphes

Un graphe est un ensemble de sommets reliés par des arêtes. Les graphes sont utilisés pour modéliser des relations entre des objets, comme les réseaux sociaux, les réseaux de transport, les réseaux de communication, etc. Les graphes peuvent être orientés ou non orientés, selon que les arêtes ont une direction ou non. Les graphes peuvent également être pondérés, c'est-à-dire que les arêtes ont un poids ou une valeur associée.

TP : Algorithmique des graphes – Réseau social des super-héros

TP : Algorithmique des graphes – Réseau social des super-héros

Introduction

Dans ce TP, vous allez manipuler un graphe représentant les relations entre super-héros et super-vilains. Vous implémenterez des algorithmes classiques (parcours en largeur, Dijkstra, centralité) pour répondre à des questions stratégiques.

1. Construction du graphe

Voici la liste des personnages et leurs relations (poids = force de la relation) :

Personnage 1 Personnage 2 Poids Type
Spider-ManIron Man3Allié proche
Spider-ManDoctor Strange1Connaissance
Spider-ManBlack Panther2Allié occasionnel
Iron ManCaptain America4Équipe
Iron ManBlack Widow3Allié proche
Iron ManAnt-Man2Allié occasionnel
Captain AmericaBlack Widow4Équipe
Captain AmericaHawkeye4Équipe
Captain AmericaHulk3Allié proche
Black WidowHawkeye3Allié proche
Black WidowScarlet Witch2Allié occasionnel
ThorLoki5Ennemi
ThorHulk2Connaissance
ThorDoctor Strange1Connaissance
LokiThanos3Allié proche
ThanosVision5Ennemi
ThanosScarlet Witch5Ennemi
Doctor StrangeScarlet Witch3Allié proche
Doctor StrangeVision2Allié occasionnel
Black PantherHulk1Connaissance
Black PantherStar-Lord2Allié occasionnel
HulkAnt-Man1Connaissance
Ant-ManHawkeye2Allié occasionnel
HawkeyeStar-Lord1Connaissance
VisionScarlet Witch4Équipe

Consigne : Construisez le graphe sous forme de dictionnaire Python (clé = sommet, valeur = liste/dictionnaire des voisins et poids).

Nous allons construire 2 dico:


graphe_non_pondere = {
    "Spider-Man": ["Iron Man", "Doctor Strange", "Black Panther"],
    "Iron Man": ["Spider-Man", "Captain America", "Black Widow", "Ant-Man"],
    "Captain America": ["Iron Man", "Black Widow", "Hawkeye", "Hulk"],
    "Black Widow": ["Iron Man", "Captain America", "Hawkeye", "Scarlet Witch"],
    "Thor": ["Loki", "Hulk", "Doctor Strange"],
    "Loki": ["Thor", "Thanos"],
    "Thanos": ["Loki", "Vision", "Scarlet Witch"],
    "Doctor Strange": ["Spider-Man", "Thor", "Scarlet Witch", "Vision"],
    "Black Panther": ["Spider-Man", "Hulk", "Star-Lord"],
    "Hulk": ["Captain America", "Thor", "Black Panther", "Ant-Man"],
    "Ant-Man": ["Iron Man", "Hulk", "Hawkeye"],
    "Hawkeye": ["Captain America", "Black Widow", "Ant-Man", "Star-Lord"],
..........

}



graphe_pondere = {
    "Spider-Man": {"Iron Man": 3, "Doctor Strange": 1, "Black Panther": 2},
    "Iron Man": {"Spider-Man": 3, "Captain America": 4, "Black Widow": 3, "Ant-Man": 2},
    "Captain America": {"Iron Man": 4, "Black Widow": 4, "Hawkeye": 4, "Hulk": 3},
    "Black Widow": {"Iron Man": 3, "Captain America": 4, "Hawkeye": 3, "Scarlet Witch": 2},
    "Thor": {"Loki": 5, "Hulk": 2, "Doctor Strange": 1},
    "Loki": {"Thor": 5, "Thanos": 3},
    "Thanos": {"Loki": 3, "Vision": 5, "Scarlet Witch": 5},
    "Doctor Strange": {"Spider-Man": 1, "Thor": 1, "Scarlet Witch": 3, "Vision": 2},
    "Black Panther": {"Spider-Man": 2, "Hulk": 1, "Star-Lord": 2},
    "Hulk": {"Captain America": 3, "Thor": 2, "Black Panther": 1, "Ant-Man": 1},
    "Ant-Man": {"Iron Man": 2, "Hulk": 1, "Hawkeye": 2},
    "Hawkeye": {"Captain America": 4, "Black Widow": 3, "Ant-Man": 2, "Star-Lord": 1},
    ..........
    
}

Maintenant, voyons ce que ça donne:

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()


for sommet in graphe_pondere:
    G.add_node(sommet)


for sommet, voisins in graphe_pondere.items():
    for voisin, poids in voisins.items():
        G.add_edge(sommet, voisin, weight=poids)


couleurs_aretes = []
for u, v, data in G.edges(data=True):
    poids = data['weight']
    if poids == 1:
        couleurs_aretes.append('gray')  # Connaissance
    elif poids == 2:
        couleurs_aretes.append('lightblue')  # Alliés occasionnels
    elif poids == 3:
        couleurs_aretes.append('green')  # Alliés proches
    elif poids == 4:
        couleurs_aretes.append('blue')  # Équipe
    elif poids == 5:
        couleurs_aretes.append('red')  # Ennemis


pos = nx.spring_layout(G, seed=42)  # Positionnement des sommets
nx.draw(G, pos, with_labels=True, node_size=2000, node_color="lightblue", font_size=10, font_weight="bold", edge_color=couleurs_aretes, width=2)


etiquettes_aretes = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=etiquettes_aretes)


plt.text(0.02, 0.95, "Légende :", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top')
plt.text(0.02, 0.90, "Gris : Connaissance (poids 1)", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top', color='gray')
plt.text(0.02, 0.85, "Bleu clair : Alliés occasionnels (poids 2)", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top', color='lightblue')
plt.text(0.02, 0.80, "Vert : Alliés proches (poids 3)", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top', color='green')
plt.text(0.02, 0.75, "Bleu : Équipe (poids 4)", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top', color='blue')
plt.text(0.02, 0.70, "Rouge : Ennemis (poids 5)", transform=plt.gca().transAxes, fontsize=10, verticalalignment='top', color='red')

plt.title("Réseau social des super-héros (graphe pondéré)")
plt.show()

A vous de tester, comprendre et modifier, vous pouvez être Thanos😜

Quel est le rayon et le diametre ?
Le graphe est-il complet?
Le graphe est-il connexe?
Donnez un cycle
Quelle est la taille du graphe?

2. Implémentation des algorithmes

2.1. Parcours en largeur

Implémentez l'algorithme de parcours en largeur 


from collections import deque

def parcours_en_largeur(graphe, depart, arrivee):
    parent = {depart: None}
    file_attente = deque([depart])
    print(file_attente)
    while file_attente:
        sommet_courant = file_attente.popleft()
        if sommet_courant == arrivee:
            chemin = []
            while sommet_courant is not None:
                chemin.append(sommet_courant)
                sommet_courant = parent[sommet_courant]
            return chemin[::-1]
        for voisin in graphe[sommet_courant]:
            if voisin not in parent:
                parent[voisin] = sommet_courant
                file_attente.append(voisin)
    return None

Testez et comprendre le script sur le graphe non pondéré

A quoi ça sert ?

Proposez le parcours en largeur du graphe ci-dessous à partir de A

2.2. Parcours en profondeur

Implémentez l'algorithme de parcours en profondeur pour parcourir le graphe . 



def parcours_profondeur(graphe, sommet_depart, visites=None, chemin=None):
    if visites is None:
        visites = set()
    if chemin is None:
        chemin = []
    visites.add(sommet_depart)
    chemin.append(sommet_depart)
    for voisin in graphe[sommet_depart]:
        if voisin not in visites:
            parcours_profondeur(graphe, voisin, visites, chemin)
    return chemin


def afficher_parcours_profondeur(graphe, sommet_depart):
    chemin = parcours_profondeur(graphe, sommet_depart)
    print(f"Parcours en profondeur depuis {sommet_depart} : {chemin}")
    return chemin

Testez et comprendre le script sur le graphe non pondéré

A quoi ça sert ?

Proposez le parcours en profondeur du graphe ci-dessous à partir de A

2.3. Dijkstra

Implémentez l'algorithme de Dijkstra 


import heapq

def dijkstra(graphe, depart, arrivee):
    distances = {sommet: float('inf') for sommet in graphe}
    distances[depart] = 0
    parent = {depart: None}
    tas_priorite = [(0, depart)]

    while tas_priorite:
        distance_courante, sommet_courant = heapq.heappop(tas_priorite)
        if distance_courante > distances[sommet_courant]:
            continue
        for voisin, poids in graphe[sommet_courant].items():
            distance = distance_courante + poids
            if distance < distances[voisin]:
                distances[voisin] = distance
                parent[voisin] = sommet_courant
                heapq.heappush(tas_priorite, (distance, voisin))

    chemin = []
    sommet = arrivee
    while sommet is not None:
        chemin.append(sommet)
        sommet = parent.get(sommet, None)
    return chemin[::-1]  # Retourne le chemin dans le bon sens

Testez et comprendre le script sur le graphe non pondéré

A quoi ça sert ?

Appliquez l'algorithme de Dijkstra sur le graphe ci-dessous à partir du sommet s